package practice1_100;

import java.util.Arrays;
import java.util.Comparator;

public class Practice354 {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override//实现comparator接口，进行排序，对宽做升序排序，宽相同，对高进行降序排序
            public int compare(int[] o1, int[] o2) {
                return o1[0] ==o2[0]?o2[1]-o1[1]:o1[0]-o2[0];
            }
        });

        int height[] =new int[envelopes.length];//宽升序的基础之上，存高的降序
        for (int i=0;i<height.length;i++){
            height[i]=envelopes[i][1];
        }

        //这里定义的save是存储以save[i]结尾的最长子序列的长度，
        int save[] =new int[height.length];//这里定义存储最长序列的数组
        Arrays.fill(save,1);
        save[height.length-1]=1;
        for(int j= save.length-2;j>=0;j--){
            for (int i=save.length-1;i>j;i--){
//                if(save[j]<=save[i]){
//                    if (height[j]<height[i])
//                        save[j]=save[i]+1;
//                    else
//                        save[j]=save[i];
//                }
                if(height[j]<height[i]){
                    save[j]=Math.max(save[j],save[i]+1 );
                }
            }
        }
        int temp=0;//再次循环找出最大的值
        for (int i=0;i<save.length;i++){
            temp=Math.max(temp,save[i]);
        }
        return temp;
    }



    public static void main(String[] args) {
        //[[5,4],[6,4],[6,7],[2,3]]
        int[][] a=new int[][] {{1,3},{3,5},{6,7},{6,8},{8,4},{9,5}};
        //{5,4},{6,4},{6,7},{2,3},[5,4],[6,4],[6,7],[2,3],[3,5],[2,9],[8,3],[7,10],[9,3]
        int b=new Practice354().maxEnvelopes(a);
        System.out.println(b);
         int c[]=new int[]{3,5,8,7,4,5};
          int d=new Practice354().lengthOfLIS(c);

    }

    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return len;
        }

        int[] dp = new int[len];
        Arrays.fill(dp, 1);

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

}
